{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Consecutive Ones II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaxConsecutiveOnes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大连续1的个数 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二进制数组 <code>nums</code> ，如果最多可以翻转一个 <code>0</code> ，则返回数组中连续 <code>1</code> 的最大个数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,0,1,1,0]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>翻转第一个 0 可以得到最长的连续 1。\n",
    "&nbsp;    当翻转以后，最大连续 1 的个数为 4。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,0,1,1,0,1]\n",
    "<b>输出：</b>4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums[i]</code>&nbsp;不是&nbsp;<code>0</code>&nbsp;就是&nbsp;<code>1</code>.</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果输入的数字是作为<strong> 无限流 </strong>逐个输入如何处理？换句话说，内存不能存储下所有从流中输入的数字。您可以有效地解决吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-consecutive-ones-ii](https://leetcode.cn/problems/max-consecutive-ones-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-consecutive-ones-ii](https://leetcode.cn/problems/max-consecutive-ones-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,1,1,0]', '[1,0,1,1,0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        window = {0: 0, 1: 0}\n",
    "        res = 0\n",
    "\n",
    "        for right, c in enumerate(nums):\n",
    "            window[c] += 1\n",
    "\n",
    "            while window[0] > 1:\n",
    "                d = nums[left]\n",
    "                window[d] -= 1\n",
    "                left += 1\n",
    "\n",
    "            res = max(res, right - left + 1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        now = 0\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            if nums[i] == 1:\n",
    "                now += 1\n",
    "                ans = max(ans, min(now + pre + 1, n))\n",
    "            else:\n",
    "                if i and nums[i - 1] == 0:\n",
    "                    pre = now = 0 \n",
    "                else:\n",
    "                    pre = now \n",
    "                    now = 0 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        dp1 = [0] * n\n",
    "        dp2 = [0] * n\n",
    "        dp1[0] = 1\n",
    "        dp2[0] = nums[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            if nums[i] == 1:\n",
    "                dp1[i] = dp1[i-1] + 1\n",
    "                dp2[i] = dp2[i-1] + 1\n",
    "            else:\n",
    "                dp1[i] = dp2[i-1]+1\n",
    "                dp2[i] = 0\n",
    "        print(dp1, dp2)\n",
    "        return max(dp1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "\n",
    "        left = 0\n",
    "        zero = None\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        flag = True\n",
    "        for j in range( n):\n",
    "            if nums[j] == 0:\n",
    "                if not flag:\n",
    "                    left = zero + 1\n",
    "                else:\n",
    "                    flag = False\n",
    "                zero = j\n",
    "                res = max(res,  j-left+1)\n",
    "            else:\n",
    "                res = max(res,  j-left+1)\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        maxlen=0\n",
    "        left, right = 0, 0\n",
    "        winfreq = {}\n",
    "        winfreq[0], winfreq[1] = 0, 0\n",
    "        \n",
    "        while right < n:\n",
    "            winfreq[nums[right]] += 1\n",
    "            right += 1\n",
    "            while winfreq[0] > 1:\n",
    "                winfreq[nums[left]] -= 1\n",
    "                left += 1\n",
    "            maxlen = max(maxlen, (right-left))\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        max_len, hash_map = 0, {}\n",
    "\n",
    "        start = 0\n",
    "        for end in range(len(nums)):\n",
    "            hash_map[nums[end]] = hash_map.get(nums[end], 0) + 1\n",
    "            if hash_map.get(0, 0) <= 1:\n",
    "                max_len = max(max_len, end - start + 1)\n",
    "            \n",
    "            while hash_map.get(0, 0) > 1:\n",
    "                head = nums[start]\n",
    "                hash_map[head] -= 1\n",
    "                start += 1\n",
    "        \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        left = 0\n",
    "        mid = -1\n",
    "        \n",
    "        nums.append(0)\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                continue\n",
    "\n",
    "            ret = max(ret, i - left) \n",
    "            left = mid + 1\n",
    "            mid = i\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        l = maxLength = 0\n",
    "        lastest0 = -1\n",
    "\n",
    "        for r in range(n):\n",
    "\n",
    "            if nums[r] == 0:\n",
    "\n",
    "                l = lastest0 + 1\n",
    "                lastest0 = r\n",
    "            \n",
    "            maxLength = max(maxLength, r - l + 1)\n",
    "\n",
    "        return maxLength\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        window = [0, 0]\n",
    "        res = 0\n",
    "\n",
    "        for right, c in enumerate(nums):\n",
    "            window[c] += 1\n",
    "\n",
    "            while window[0] > 1:\n",
    "                d = nums[left]\n",
    "                window[d] -= 1\n",
    "                left += 1\n",
    "\n",
    "            res = max(res, right - left + 1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        l = r = 0\n",
    "        res = 0\n",
    "        d = defaultdict(int)\n",
    "        while r < len(nums):\n",
    "            d[nums[r]] += 1\n",
    "          \n",
    "            if d[0] <= 1:\n",
    "                res = max(r - l + 1, res)\n",
    "            while d[0] > 1: \n",
    "                d[nums[l]] -= 1\n",
    "                # res -= nums[l]\n",
    "                l += 1\n",
    "                # print(d)\n",
    "\n",
    "            r += 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        l, r = -1, 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if i == r:\n",
    "                r += 1\n",
    "                while r < n and nums[r]:\n",
    "                    r += 1\n",
    "            ans = max(ans, r - l - 1)\n",
    "            if not x:\n",
    "                l = i\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        # left存第一组连续的1的最左下标\n",
    "        # 开始下面的for循环时肯定要从第一个字符开始处理，所以初始化为0\n",
    "        left = 0\n",
    "        # mid存中间的那个0的下标\n",
    "        # 初始值设置为-1是为了保证结算一次之后left变成0\n",
    "        mid = -1\n",
    "        \n",
    "        # 强制触发最后一次结算\n",
    "        nums.append(0)\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                continue\n",
    "\n",
    "            #  0111111011111110\n",
    "            #  .x....mid......i\n",
    "            ret = max(ret, i - left) \n",
    "            left = mid + 1\n",
    "            mid = i\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        l,r,res,cur=0,0,0,0\n",
    "        while r<len(nums):\n",
    "            cur += nums[r]\n",
    "            while r-l>cur:\n",
    "                cur-=nums[l]\n",
    "                l+=1\n",
    "            res =max(res,r-l+1)\n",
    "            r+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        ret = 1\n",
    "        lst = -1\n",
    "        crt = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                crt += 1\n",
    "                ret = max(ret, crt + lst + 1)\n",
    "            else:\n",
    "                lst = crt\n",
    "                crt = 0\n",
    "                ret = max(ret, lst+1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        maxlen=0\n",
    "        left, right = 0, 0\n",
    "        winfreq = {}\n",
    "        winfreq[0], winfreq[1] = 0, 0\n",
    "        \n",
    "        while right < n:\n",
    "            winfreq[nums[right]] += 1\n",
    "            right += 1\n",
    "            while winfreq[0] > 1:\n",
    "                winfreq[nums[left]] -= 1\n",
    "                left += 1\n",
    "            maxlen = max(maxlen, (right-left))\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        res, prev, cnt = 0, 0, 0\n",
    "        for num in nums:\n",
    "            cnt += 1\n",
    "            if num == 0:\n",
    "                prev = cnt\n",
    "                cnt = 0\n",
    "            res = max(res, prev + cnt)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        res, prev, cnt = 0, 0, 0\n",
    "        for num in nums:\n",
    "            cnt += 1\n",
    "            if num == 0:\n",
    "                prev = cnt\n",
    "                cnt = 0\n",
    "            res = max(res, prev + cnt)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        l,r,cur,res=0,0,0,0\n",
    "        while r<len(nums):\n",
    "            cur+= nums[r]\n",
    "            while r-l>cur:\n",
    "                cur-=nums[l]\n",
    "                l+=1\n",
    "            res=max(res,r-l+1)\n",
    "            r+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        left = 0\n",
    "        mid = -1\n",
    "        \n",
    "        nums.append(0)\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                continue\n",
    "\n",
    "            ret = max(ret, i - left) \n",
    "            left = mid + 1\n",
    "            mid = i\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        l = 0\n",
    "        k = 1\n",
    "        for r in range(len(nums)):\n",
    "            if nums[r] == 0:\n",
    "                k -= 1\n",
    "            while k < 0:\n",
    "                if nums[l] == 0:\n",
    "                    k += 1\n",
    "                l += 1\n",
    "            res = max(res, r -l + 1)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        # condition: number of 0 in hashmap should less than 1\n",
    "        cnt = {}\n",
    "        max_len = 0\n",
    "\n",
    "        left = 0\n",
    "        for right in range(len(nums)):\n",
    "            num = nums[right]\n",
    "            cnt[num] = cnt.get(num, 0) + 1\n",
    "\n",
    "            if cnt.get(0, 0) <= 1:\n",
    "                max_len = max(max_len, right - left + 1)\n",
    "            \n",
    "\n",
    "            while cnt.get(0, 0) > 1:\n",
    "                num = nums[left]\n",
    "                cnt[num] -= 1\n",
    "                if cnt[num] == 0:\n",
    "                    del cnt[num]\n",
    "                left += 1\n",
    "        return max_len "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        if sum(nums) == len(nums): return len(nums)\n",
    "        n = len(nums)\n",
    "        prev = -1\n",
    "        L = [0] * n\n",
    "        R = [n] * n\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "\n",
    "            if num == 0:\n",
    "                L[i] = prev\n",
    "                if prev != -1:\n",
    "                    R[prev] = i\n",
    "                prev = i\n",
    "        \n",
    "        res = 1\n",
    "        for i in range(n):\n",
    "\n",
    "            if nums[i] == 0:\n",
    "\n",
    "                res = max(res, R[i] - 1 - L[i])\n",
    "\n",
    "        return res\n",
    "        # print(L, R)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "       \n",
    "        # 00, 1,1,0\n",
    "        # 4 - 1 - 1 = 2\n",
    "        # 1 - 0 = \n",
    "        # 00, 0,1,0\n",
    "        # 4 - 2 - 1 = 1\n",
    "        # 2 - 1 = 1\n",
    "\n",
    "        # 0 \n",
    "        # 00,0 0, 0\n",
    "        # 3 - 2 - 1 = 0\n",
    "        # 2 - 1 = 1\n",
    "        # 3 - 1  - 2\n",
    "        #append leading 0 and ending 0 \n",
    "        # nums = [0,0] + nums + [0]\n",
    "        n = len(nums)\n",
    "        right = 0\n",
    "        zero_indx = [1,1]\n",
    "        res = 0\n",
    "        #find three 0 that has longest distance\n",
    "        while right < n:\n",
    "            if nums[right] == 0:\n",
    "                zero_indx.append(right+2)\n",
    "            right += 1\n",
    "            if len(zero_indx) == 4:\n",
    "                zero_indx.pop(0)\n",
    "            if len(zero_indx) == 3:\n",
    "                res = max(res, zero_indx[2] - zero_indx[1] - 1 + zero_indx[1] - zero_indx[0] )\n",
    "        if len(zero_indx) == 3:\n",
    "            zero_indx.pop(0)\n",
    "        res = max(res, n + 2 - zero_indx[1] - 1 + zero_indx[1] - zero_indx[0])\n",
    "        return res\n",
    "\n",
    "        # while right < n:\n",
    "        #     if nums[right] == 0:\n",
    "        #         zero_indx.append(right)\n",
    "        #     right += 1\n",
    "        #     if len(zero_indx) == 4:\n",
    "        #         zero_indx.pop(0)\n",
    "        #     if len(zero_indx) == 3:\n",
    "        #         dist_tail = zero_indx[2] - zero_indx[1] - 1\n",
    "        #         dist_head = zero_indx[1] - zero_indx[0] if zero_indx[1] != 1 else 0 \n",
    "        #         res = max(res, dist_head + dist_tail)\n",
    "        # return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        zero_pos = [-1]\n",
    "        for i, v in enumerate(nums):\n",
    "            if v == 0:\n",
    "                zero_pos.append(i)\n",
    "\n",
    "        zero_pos.append(len(nums))\n",
    "\n",
    "        if len(zero_pos) == 2:\n",
    "            return len(nums)\n",
    "        else:\n",
    "            return max(end - begin - 1 for end, begin in zip(zero_pos[2:], zero_pos[:-2]))\n",
    "\n",
    "# class Solution:\n",
    "#     def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "#         res,dp1,dp0 = 0,0,0\n",
    "#         for i in range(len(nums)):\n",
    "#             if nums[i] == 1:\n",
    "#                 dp0+=1\n",
    "#                 dp1+=1\n",
    "#             else:\n",
    "#                 dp1 = dp0+1\n",
    "#                 dp0 = 0 \n",
    "#             res = max(res,dp0,dp1)\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        max_nums,hashmap=0,{}\n",
    "        start=0\n",
    "        for i in range(len(nums)):\n",
    "            hashmap[nums[i]]=1+hashmap.get(nums[i],0)\n",
    "            print(hashmap)\n",
    "            if hashmap.get(0, 0) > 1:\n",
    "                hashmap[nums[start]] -= 1\n",
    "                start += 1\n",
    "            print(hashmap)\n",
    "            max_nums=max(max_nums,i-start+1)\n",
    "            print()\n",
    "        return max_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        max_len = 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        zero_positions = []\n",
    "\n",
    "        while left<len(nums) and right<len(nums):\n",
    "            if nums[right]==1:\n",
    "                max_len = max(max_len, right-left+1)\n",
    "                right += 1\n",
    "            else:\n",
    "                if len(zero_positions)==0:\n",
    "                    zero_positions.append(right)\n",
    "                    max_len = max(max_len, right-left+1)\n",
    "                    right += 1\n",
    "                else:\n",
    "                    left = zero_positions[-1]+1\n",
    "                    zero_positions.append(right)\n",
    "                    max_len = max(max_len, right-left+1)\n",
    "                    right += 1\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        max_count = 0\n",
    "        start = 0\n",
    "        first_zero = True\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 1:\n",
    "                max_count += 1\n",
    "            elif nums[i] == 0 and first_zero:\n",
    "                max_count += 1\n",
    "                start = i\n",
    "                first_zero = False\n",
    "            else:\n",
    "                max_count = i - start\n",
    "                start = i\n",
    "            result= max(result, max_count)\n",
    "            print(result, max_count, start)\n",
    "        result= max(result, max_count)\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        max_nums,hashmap=0,{}\n",
    "        start=0\n",
    "        for i in range(len(nums)):\n",
    "            hashmap[nums[i]]=1+hashmap.get(nums[i],0)\n",
    "            print(hashmap)\n",
    "            if hashmap.get(0, 0) > 1:\n",
    "                hashmap[nums[start]] -= 1\n",
    "                start += 1\n",
    "            print(hashmap)\n",
    "            max_nums=max(max_nums,i-start+1)\n",
    "            print()\n",
    "        return max_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # dp[i][0]表示该位置不翻转的结果\n",
    "        # dp[i][1]表示该位置翻转的结果\n",
    "        dp = [[0]*2 for _ in range(n+1)]\n",
    "        if nums[0] == 1:\n",
    "            dp[1] = [1, 1]\n",
    "        else:\n",
    "            dp[1] = [0, 1]\n",
    "        for k in range(2,n+1):\n",
    "            if nums[k-1]==1:\n",
    "                dp[k][0] = dp[k-1][0] + 1\n",
    "                dp[k][1] = dp[k-1][1] + 1\n",
    "            else:\n",
    "                dp[k][0] = 0\n",
    "                dp[k][1] = dp[k-1][0] + 1\n",
    "        res = 0\n",
    "        for x in dp:\n",
    "            res = max(res, x[1])\n",
    "        return res\n",
    "\n",
    "# # 朴素二维dp\n",
    "# class Solution:\n",
    "#     def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "#         # 只在当前i位置上的数，考虑翻转\n",
    "#         # dp[i][0]表示该位置不翻转的结果，dp[i][1]表示该位置翻转的结果\n",
    "#         dp = [[0,0] for num in nums]\n",
    "#         if nums[0]==1:\n",
    "#             dp[0] = [1,1]\n",
    "#         else:\n",
    "#             dp[0] = [0,1]\n",
    "        \n",
    "#         for i in range(1,len(nums)):\n",
    "#             if nums[i]==1:\n",
    "#                 dp[i][0],dp[i][1] = dp[i-1][0]+1,dp[i-1][1]+1 #当前位为1两个数都++\n",
    "#             else:\n",
    "#                 dp[i][0] = 0\n",
    "#                 dp[i][1] = dp[i-1][0]+1  #当前位为0，不翻转就是0了，翻转接上之前的不翻转的值\n",
    "#         res = 0\n",
    "#         for x in dp:\n",
    "#             res = max(res, x[1])\n",
    "#         return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        n = len(nums)\n",
    "\n",
    "        def check(x):\n",
    "            for i in range(n - x + 1):\n",
    "                tmp = acc[i + x] - acc[i]\n",
    "                if tmp + 1 >= x:\n",
    "                    return True \n",
    "            return False \n",
    "        \n",
    "        low, high =1, n \n",
    "        ans = 1\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0,0] for _ in range(n+1)]\n",
    "        res = 0\n",
    "        for i in range(1,n+1):\n",
    "            if nums[i-1] == 1:\n",
    "                dp[i][0] = dp[i-1][0]+1\n",
    "                dp[i][1] = dp[i-1][1]+1\n",
    "            else:\n",
    "                dp[i][0] = 0 \n",
    "                dp[i][1] = dp[i-1][0]+1\n",
    "            res = max(res,dp[i][0],dp[i][1])\n",
    "        return res\n",
    "           \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "\n",
    "        dp = [[0]*2 for _ in range(len(nums))]\n",
    "        if nums[0] == 0 :\n",
    "            dp[0][0] = 0 # 保持状态\n",
    "            dp[0][1] = 1 # 翻转\n",
    "\n",
    "        else :\n",
    "            dp[0][0] = 1\n",
    "            dp[0][1] = 1\n",
    "\n",
    "        result = max(dp[0])\n",
    "\n",
    "        for i in range(1, len(nums)) :\n",
    "            if nums[i] == 0 :\n",
    "                dp[i][0] = 0\n",
    "                dp[i][1] = dp[i-1][0] +1\n",
    "\n",
    "            else :\n",
    "                if i-1>=0 and nums[i-1] == 0 :\n",
    "                    dp[i][0] = 1\n",
    "                else :\n",
    "                    dp[i][0] = dp[i-1][0] + 1\n",
    "\n",
    "                dp[i][1] = dp[i-1][1] +1\n",
    "            result = max(result, dp[i][0], dp[i][1])\n",
    "        #print(dp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pos = deque()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                if not pos:\n",
    "                    pos.append([i, i])\n",
    "                else:\n",
    "                    pos.append([i, i - pos[0][0]- 1])    \n",
    "            if len(pos) == 2:\n",
    "                ans = max(ans, pos[0][1] + pos[1][1] + 1)\n",
    "                pos.popleft()\n",
    "            elif len(pos) == 1:\n",
    "                ans = max(ans, i - pos[0][0] + 1 + pos[0][1] )\n",
    "                print(ans)\n",
    "            else:\n",
    "                ans = max(ans, i + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        '''\n",
    "        dp[i][j]\n",
    "        '''\n",
    "        dp = [[0 for _ in range(2)] for _ in range(n+1)]\n",
    "        result = 0\n",
    "        for i in range(1, n+1):\n",
    "            if nums[i-1] == 0:\n",
    "                dp[i][0] = 0\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            else:\n",
    "                dp[i][0] = max(dp[i-1][0], dp[i-1][0]) + 1\n",
    "                dp[i][1] = dp[i-1][1] + 1\n",
    "            result = max([result, dp[i][0], dp[i][1]])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]*(n+1)\n",
    "        result = 0\n",
    "        flag = -1\n",
    "        for i in range(n):\n",
    "            if nums[i]==1:\n",
    "                dp[i+1] = dp[i] + 1\n",
    "                \n",
    "            else:\n",
    "                \n",
    "                dp[i+1] = i-flag\n",
    "                flag = i\n",
    "                \n",
    "                    \n",
    "            result = max(result,dp[i+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        print([i for i, x in enumerate(nums) if x == 0])\n",
    "        index_0 = [i for i, x in enumerate(nums) if x == 0]\n",
    "        if len(index_0) <= 1: return len(nums)\n",
    "        if len(index_0) == 2: return max(index_0[-1], len(nums)-1-index_0[0])\n",
    "        max_length = 0\n",
    "        for i in range(len(index_0)-1):\n",
    "            print(index_0[i+1], index_0[i-1])\n",
    "            if i == 0 and index_0[i+1] >= max_length:\n",
    "                max_length = index_0[i+1]\n",
    "            # elif i == len(index_0)-1 and len(nums) - 1 - index_0[i-1] >= max_length:\n",
    "                # max_length = len(nums) - 1 - index_0[i-1]\n",
    "            elif index_0[i+1] - index_0[i-1] - 1 >= max_length:\n",
    "                max_length = index_0[i+1] - index_0[i-1] - 1\n",
    "        return max(max_length, len(nums) - 1 - index_0[i])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0 for _ in range(2)] for i in range(n + 1)]\n",
    "        res = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if nums[i - 1] == 1:\n",
    "                dp[i][0] = dp[i - 1][0] + 1\n",
    "                dp[i][1] = dp[i - 1][1] + 1\n",
    "\n",
    "            else:\n",
    "                dp[i][0] = dp[i - 1][1] + 1\n",
    "                dp[i][1] = 0\n",
    "            res = max(res, dp[i][0])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return 1\n",
    "        if 0 not in nums:\n",
    "            return len(nums)\n",
    "\n",
    "        help_arr=[]\n",
    "        a=1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]!=0:\n",
    "                break \n",
    "        nums=nums[i:]\n",
    "\n",
    "        count=0\n",
    "        for n in nums:\n",
    "            if n==a:\n",
    "                count+=1\n",
    "            else:\n",
    "                help_arr.append(count)\n",
    "                a=(a+1)%2\n",
    "                count=1\n",
    "\n",
    "        help_arr.append(count)\n",
    "\n",
    "\n",
    "\n",
    "        help_arr2=[]\n",
    "        tmp=[]\n",
    "        for i in range(len(help_arr)):\n",
    "            if i%2==0:\n",
    "                tmp.append(help_arr[i])\n",
    "            else:\n",
    "                if help_arr[i]==1:\n",
    "                    continue\n",
    "\n",
    "                else:\n",
    "                    help_arr2.append([i for i in tmp])\n",
    "                    tmp=[]\n",
    "        help_arr2.append(tmp)\n",
    "        res=1\n",
    "        for arr in help_arr2:\n",
    "            if len(arr)==0:\n",
    "                continue\n",
    "            elif len(arr)==1:\n",
    "                if res<arr[0]+1:\n",
    "                    res=arr[0]+1\n",
    "\n",
    "            \n",
    "            for i in range(len(arr)-1):\n",
    "                k=  arr[i]+arr[i+1]+1\n",
    "                if k>res:\n",
    "                    res=k \n",
    "        print(help_arr,help_arr2)\n",
    "        return res \n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        doc = []\n",
    "        val = nums[0]\n",
    "        l = 0\n",
    "        for x in nums:\n",
    "            if x == val:\n",
    "                l += 1\n",
    "            \n",
    "            else:\n",
    "                doc.append((val, l))\n",
    "                val = x\n",
    "                l = 1\n",
    "        doc.append((val, l))\n",
    "        \n",
    "        prevl = 0\n",
    "        result = 0\n",
    "        print(doc)\n",
    "        for val, l in doc:\n",
    "            if val == 1:\n",
    "                result = max(result, l + prevl)\n",
    "                prevl = l\n",
    "\n",
    "            if val == 0:\n",
    "                result = max(result, prevl + 1)\n",
    "                if l > 1:\n",
    "                    prevl = 1\n",
    "                else:\n",
    "                    prevl += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix, suffix = [0] * n, [0] * n\n",
    "        prefix[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 1:\n",
    "                prefix[i] = prefix[i - 1] + 1\n",
    "        suffix[-1] = nums[-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] == 1:\n",
    "                suffix[i] = suffix[i + 1] + 1\n",
    "        maxCount = 0\n",
    "        for i in range(n):\n",
    "            preSum, sufSum = 0, 0\n",
    "            if i > 0:\n",
    "                preSum = prefix[i - 1]\n",
    "            if i < n - 1:\n",
    "                sufSum = suffix[i + 1]\n",
    "            maxCount = max(maxCount, preSum + sufSum + 1)\n",
    "        return maxCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        dp=[[0 for _ in range(2)] for _ in range(len(nums))]\n",
    "\n",
    "        dp[0][1]=1 if nums[0]==1 else 0\n",
    "        dp[0][0]=1 if nums[0]==0 else 0\n",
    "        res=max(dp[0][1],dp[0][0])\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]==1:\n",
    "                dp[i][0]=dp[i-1][0]+1\n",
    "                dp[i][1]=dp[i-1][1]+1\n",
    "            else:\n",
    "                dp[i][0]=dp[i-1][1]+1\n",
    "                dp[i][1]=0\n",
    "            res=max(res,dp[i][0],dp[i][1])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        nums_1 = ''.join([str(x) for x in nums])\n",
    "        nums_1 = nums_1.split('0')\n",
    "        if len(nums_1) <= 2:\n",
    "            return len(nums)\n",
    "        if list(set(nums)) == [0]:\n",
    "            return 1\n",
    "        max_length = 1\n",
    "        for i in range(len(nums_1) - 1):\n",
    "            max_length = max(max_length, len(nums_1[i]) + len(nums_1[i + 1]))\n",
    "        return max_length + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0 for _ in range(n)]\n",
    "        suf = [0 for _ in range(n)]\n",
    "        pre[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 1:\n",
    "                pre[i] = pre[i - 1] + 1\n",
    "            else:\n",
    "                pre[i] = 0\n",
    "        suf[-1] = nums[-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] == 1:\n",
    "                suf[i] = suf[i + 1] + 1\n",
    "            else:\n",
    "                suf[i] = 0\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x:\n",
    "                ans = max(ans, pre[i] + suf[i] - 1)\n",
    "            else:\n",
    "                ans = max(ans, pre[max(0, i - 1)] + suf[min(n - 1, i + 1)] + 1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        dp = [[0] * (m+1) for _ in range(2)]\n",
    "  \n",
    "        for i in range(1,m+1):\n",
    "            if nums[i-1] == 0:\n",
    "                dp[0][i] = 0\n",
    "                dp[1][i] = dp[0][i-1] + 1\n",
    "            else:\n",
    "                dp[0][i] = dp[0][i-1] + 1\n",
    "                dp[1][i] = dp[1][i-1] + 1\n",
    "        return max(max(dp[0]), max(dp[1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        dp = [[0] * (m+1) for _ in range(2)]\n",
    "        if nums[0] == 1:\n",
    "            dp[0][1] = 1\n",
    "            dp[1][1] = 0\n",
    "        if nums[0] == 0:\n",
    "            dp[0][1] = 0\n",
    "            dp[1][1] = 1\n",
    "        for i in range(1,m+1):\n",
    "            if nums[i-1] == 0:\n",
    "                dp[0][i] = 0\n",
    "                dp[1][i] = dp[0][i-1] + 1\n",
    "            else:\n",
    "                dp[0][i] = dp[0][i-1] + 1\n",
    "                dp[1][i] = dp[1][i-1] + 1\n",
    "        return max(max(dp[0]), max(dp[1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        maxOneUse =[ 0] * n\n",
    "        maxOneUn = [0] * n \n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            maxOneUn[i] = maxOneUn[i-1] + 1 if nums[i] == 1 else 0\n",
    "            maxOneUse[i] = maxOneUse[i-1] + 1 if nums[i] == 1 else maxOneUn[i-1] + 1\n",
    "\n",
    "            ret = max(max(maxOneUn[i],maxOneUse[i]),ret)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0 for _ in range(n)]\n",
    "        suf = [0 for _ in range(n)]\n",
    "        pre[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 1:\n",
    "                pre[i] = pre[i - 1] + 1\n",
    "            else:\n",
    "                pre[i] = 0\n",
    "        suf[-1] = nums[-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] == 1:\n",
    "                suf[i] = suf[i + 1] + 1\n",
    "            else:\n",
    "                suf[i] = 0\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x:\n",
    "                ans = max(ans, pre[i] + suf[i] - 1)\n",
    "            else:\n",
    "                ans = max(ans, pre[max(0, i - 1)] + suf[min(n - 1, i + 1)] + 1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        ans = ''.join([str(num) for num in nums])\n",
    "        ans = ans.split('0')\n",
    "        cnt = [len(item) for item in ans]\n",
    "        # print(cnt)\n",
    "        if len(cnt) == 1:\n",
    "            return cnt[0]\n",
    "        else:\n",
    "            return max([a + b + 1 for a, b in zip(cnt[:-1], cnt[1:])])  # 0 可以反转为1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        lpmatrix, rpmatrix = [], []\n",
    "        if sum(nums) == len(nums):\n",
    "            return len(nums)\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                cnt = 0\n",
    "            else:\n",
    "                cnt += 1\n",
    "            lpmatrix.append(cnt)\n",
    "        cnt = 0\n",
    "        for num in nums[::-1]:\n",
    "            if num == 0:\n",
    "                cnt = 0\n",
    "            else:\n",
    "                cnt += 1\n",
    "            rpmatrix.append(cnt)\n",
    "        rpmatrix = rpmatrix[::-1] + [0]\n",
    "        lpmatrix = [0] + lpmatrix \n",
    "        length = len(nums)\n",
    "        ans = 1\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                ans = max(ans, 1 + lpmatrix[i] + rpmatrix[i+1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int: \n",
    "        pre_num = [0 for i in range(len(nums))]\n",
    "        sub_num = [0 for i in range(len(nums))]\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i - 1] == 1:\n",
    "                pre_num[i] = pre_num[i - 1] + 1\n",
    "            else:\n",
    "                pre_num[i] = 0\n",
    "        \n",
    "        for j in range(len(nums) - 2, -1, -1):\n",
    "            if nums[j + 1] == 1:\n",
    "                sub_num[j] = sub_num[j + 1] + 1\n",
    "            else:\n",
    "                sub_num[j] = 0\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(len(nums)):\n",
    "            ans = max(ans, pre_num[i] + sub_num[i] + 1)\n",
    "        \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0 for _ in range(n)]\n",
    "        suf = [0 for _ in range(n)]\n",
    "        pre[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 1:\n",
    "                pre[i] = pre[i - 1] + 1\n",
    "            else:\n",
    "                pre[i] = 0\n",
    "        suf[-1] = nums[-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] == 1:\n",
    "                suf[i] = suf[i + 1] + 1\n",
    "            else:\n",
    "                suf[i] = 0\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x:\n",
    "                ans = max(ans, pre[i] + suf[i] - 1)\n",
    "            else:\n",
    "                ans = max(ans, pre[max(0, i - 1)] + suf[min(n - 1, i + 1)] + 1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "\n",
    "        dp = [[0,0,0] for _ in range(len(nums))]\n",
    "\n",
    "        dp[0][0] = nums[0]\n",
    "        dp[0][1] = 1\n",
    "        dp[0][2] = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i][0] = (dp[i-1][0]*nums[i]) + nums[i]\n",
    "            dp[i][1] = dp[i-1][0] + 1\n",
    "            dp[i][2] = max(dp[i-1][1],dp[i-1][2])*nums[i]+nums[i]\n",
    "        print(dp)\n",
    "        return max(map(lambda x: max(x), dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0] * n\n",
    "        suf = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i :\n",
    "                pre[i] = pre[i-1]\n",
    "            if nums[i] :\n",
    "                pre[i] += 1\n",
    "            else:\n",
    "                pre[i] = 0 \n",
    "            ans = max(ans, pre[i])\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if i < n-1:\n",
    "                suf[i] = suf[i+1]\n",
    "            if nums[i]:\n",
    "                suf[i] += 1\n",
    "            else:\n",
    "                suf[i] = 0\n",
    "        print(suf)\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                res = 0\n",
    "                if i > 0 :\n",
    "                    res += pre[i-1]\n",
    "                if i < n - 1:\n",
    "                    res += suf[i+1]\n",
    "                ans = max(ans, res+1)\n",
    "        print(pre, suf)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
    "        #动态规划\n",
    "        n=len(nums)\n",
    "        dp=[[0,0] for _ in range(n+1)]\n",
    "        max_ans=0\n",
    "        for i in range(1,n+1):\n",
    "            if nums[i-1]==1:\n",
    "                dp[i][0]=dp[i-1][0]+1\n",
    "                dp[i][1]=dp[i-1][1]+1\n",
    "            else:\n",
    "                #反转时\n",
    "                dp[i][0]=0\n",
    "                dp[i][1]=dp[i-1][0]+1\n",
    "            max_ans=max(max_ans,dp[i][0],dp[i][1])\n",
    "        return max_ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
